package com.hdu.other.monotonyQueue;

import java.util.Arrays;

public class lc2071 {
    class Solution {
        public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
            int wLen = workers.length;
            Arrays.sort(tasks);
            Arrays.sort(workers);

            int l = 0;
            int r = Math.min(tasks.length, workers.length);

            int ans = 0;
            while (l <= r) {
                int mid = l + (r - l + 1) / 2;
                if (f(tasks, workers, 0, mid - 1, wLen - mid, wLen - 1, pills, strength)) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            return ans;
        }

        private boolean f(int[] tasks, int[] workers, int tl, int tr, int wl, int wr, int pills, int strength) {
            int tLen = tr - tl + 1;
            int[] q = new int[tLen];
            int h = 0, r = 0;
            for (int i = wl; i < wr; i++) {
                while (tl <= tr && workers[i] >= tasks[tl]) {
                    q[r++] = tl++;
                }
                if (h < r && workers[i] >= tasks[q[h]]) h++;
                else {
                    pills--;
                    while (tl <= tr && workers[i] + strength >= tasks[tl]) {
                        q[r++] = tl++;
                    }
                    if (h >= r || workers[i] + strength < tasks[q[r - 1]]) return false;
                    if (h < r && workers[i] + strength >= tasks[q[r - 1]]) r--;
                }
            }
            return pills >= 0;
        }
    }

}
